import java.util.LinkedList;
import java.util.Queue;

public class Test {

    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};




    //地图分析
    public int maxDistance(int[][] grid){
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = -1;
            }
        }
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1){
                    dist[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }
        int ret = -1;
        while (!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b= t[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i] , y = b+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1){
                    dist[x][y] = dist[a][b]+1;
                    q.add(new int[]{x,y});
                    ret = Math.max(ret,dist[x][y]);
                }
            }
        }
        return ret;
    }




    //地图中的最高点
    public int[][] highestpeak(int[][] isWater){
        int m = isWater.length, n = isWater[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] =-1;
            }
        }
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1){
                    dist[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }

        while (!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i], y = b+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1){
                    dist[x][y] = dist[a][b] +1;
                    q.add(new int[]{x,y});
                }
            }
        }
        return dist;
    }


    //飞地的数量
    public int numEnclaves(int[][] grid){
        int m = grid.length, n= grid[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i==0 || i==m-1 || j==0 || j==n-1){
                    if (grid[i][j] == 1){
                        q.add(new int[]{i,j});
                        vis[i][j] = true;
                    }
                }
            }
        }

        while (!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int i = 0; i < 4; i++) {
                int x= a+dx[i], y = b+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && grid[x][y]== 1 && !vis[x][y]){
                    q.add(new int[]{x,y});
                    vis[x][y] = true;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]){
                    ret++;
                }
            }
        }
        return ret;
    }




    //矩阵
    public int[][] updateMatrix(int[][] mat){
        int m= mat.length, n= mat[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = -1;
            }
        }
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0){
                    dist[i][j] = 0;
                    q.add(new int[]{i,j});
                }
            }
        }
        while (!q.isEmpty()){
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int i = 0; i < 4; i++) {
                int x = a+dx[i], y = b+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && dist[x][y] == -1){
                    dist[x][y] = dist[a][b]+1;
                    q.add(new int[]{x,y});
                }
            }
        }
        return dist;
    }



}
